package com.example;

import java.util.LinkedList;
import java.util.List;

/**
 * @Author loubobooo
 * @Description #22括号生成
 * @Date 2019/11/25 9:44
 **/
public class GenerateParentheses {

    /**
     * @Author loubobooo
     * @Description 给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。
     * @Date 2019/11/25 9:44
     * @Param
     * @return
     **/
//    public List<String> generateParenthesis(int n) {
//        if (n == 0) {
//            return new ArrayList<>();
//        }
//        // 1. 定义含义dp[i]为括号能够生成的组合
//        // 2. 定义关系式dp[i] = "(" + dp[j] + ")" + dp[i -j -1],数组从0开始，因此要减一
//        // 3. 找出初始值dp[0] = "", dp[1] = "()", dp[2] = "()()","(())";
//        List<String> dp0 = new ArrayList<>();
//        dp0.add("");
//        List<List<String>> dp = new ArrayList<>();
//        dp.add(dp0);
//        for (int i = 1; i <= n; i++) {
//            List<String> curResult = new ArrayList<>();
//            for (int j = 0; j < i; j++) {
//                List<String> list1 = dp.get(j);
//                List<String> list2 = dp.get(i - j - 1);
//                for (String str1: list1) {
//                    for (String str2: list2) {
//                        curResult.add("(" + str1 + ")" + str2);
//                    }
//                }
//            }
//            dp.add(curResult);
//        }
//        return dp.get(n);
//    }

    private List<String> list = new LinkedList<>();

    public List<String> generateParenthesis(int n) {
        backtracking(n, n, "");
        return list;
    }

    private void backtracking(int left, int right, String s) {
        if (left == 0 && right == 0) {
            list.add(s);
            return;
        }
        if (left > 0) {
            backtracking(left - 1, right, s + "(");
        }
        // 已经生成的右括号要少于左括号
        if (left < right) {
            backtracking(left, right - 1, s + ")");
        }
    }

    public static void main(String[] args) {
        GenerateParentheses g = new GenerateParentheses();
        List<String> l = g.generateParenthesis(3);
        System.out.println(l.size());
        l.forEach(k -> {
            System.out.println(k);
        });
    }

}
